#include <bits/stdc++.h>

const int P = 1004535809, R = 3;

int plus(const int x, const int y) {
    return (x + y >= P) ? (x + y - P) : (x + y);
}
int times(const int x, const int y) {
    return (long long) x * y % P;
}
int power(int a, int b) {
    int r = 1;
    while (b) {
        if (b & 1) r = times(r, a);
        a = times(a, a);
        b >>= 1;
    }
    return r;
}

void dft(std::vector<int> &a) {
    static std::vector<int> rev, roots{0, 1};
    int n = a.size();
    if (int(rev.size()) != n) {
        int k = __builtin_ctz(n) - 1;
        rev.resize(n);
        for (int i = 0; i < n; ++i)
            rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << k);
    }
    for (int i = 0; i < n; ++i)
        if (rev[i] < i) std::swap(a[rev[i]], a[i]);
    if (int(roots.size()) < n) {
        int k = __builtin_ctz(roots.size());
        roots.resize(n);
        while ((1 << k) < n) {
            int wn = power(R, (P - 1) >> (k + 1));
            for (int i = 1 << (k - 1); i < (1 << k); ++i) {
                roots[i * 2] = roots[i];
                roots[i * 2 + 1] = times(roots[i], wn);
            }
            ++k;
        }
    }
    for (int k = 1; k < n; k *= 2) {
        for (int i = 0; i < n; i += k * 2) {
            for (int j = 0; j < k; ++j) {
                int x = a[i + j];
                int y = times(a[i + k + j], roots[k + j]);
                a[i + j] = plus(x, y);
                a[i + k + j] = plus(x, P - y);
            }
        }
    }
}

void idft(std::vector<int> &a) {
    int n = a.size();
    std::reverse(a.begin() + 1, a.end());
    dft(a);
    int invn = power(n, P - 2);
    for (int i = 0; i < n; ++i) a[i] = times(a[i], invn);
}

std::vector<int> conv(std::vector<int> a, std::vector<int> b, int m) {
    int tot = a.size() + b.size() - 1;
    int n = 1;
    while (n < tot) n *= 2;
    std::vector<int> res(n);
    a.resize(n);
    b.resize(n);
    dft(a);
    dft(b);
    for (int i = 0; i < n; ++i) res[i] = times(a[i], b[i]);
    idft(res);
    for (int i = m; i < n; ++i) res[i % m] = plus(res[i % m], res[i]);
    res.resize(m);
    return res;
}

int power(int a, int b, int p) {
    int r = 1;
    while (b) {
        if (b & 1) r = 1ll * r * a % p;
        a = 1ll * a * a % p;
        b >>= 1;
    }
    return r;
}

int get_root(int p) {
    std::vector<int> r;
    int t = p - 1;
    for (int i = 2; i * i <= t; ++i) {
        if (t % i == 0) {
            r.push_back((p - 1) / i);
            while (t % i == 0) t /= i;
        }
    }
    if (t > 1) r.push_back((p - 1) / t);
    for (int i = 2; i <= p - 1; ++i) {
        bool ok = true;
        for (int j : r) {
            if (power(i, j, p) == 1) {
                ok = false;
                break;
            }
        }
        if (ok) return i;
    }
    return assert(false), -1;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, p, x, S;
    std::cin >> n >> p >> x >> S;
    std::vector<int> log(p);
    int g = get_root(p);
    for (int i = 0, gk = 1; i <= p - 2; ++i, gk = 1ll * gk * g % p)
        log[gk] = i;
    --p;
    std::vector<int> a(p);
    for (int i = 0; i < S; ++i) {
        int k;
        std::cin >> k;
        if (k) ++a[log[k]]; // bug
    }
    std::vector<int> ans{1};
    while (n) {
        if (n & 1) ans = conv(ans, a, p);
        a = conv(a, a, p);
        n >>= 1;
    }
    std::cout << ans[log[x]] << '\n';
    
    return 0;
}